home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / test / test_deque.py < prev    next >
Text File  |  2005-10-18  |  19KB  |  656 lines
  1. from collections import deque
  2. import unittest
  3. from test import test_support
  4. from weakref import proxy
  5. import copy
  6. import cPickle as pickle
  7. from cStringIO import StringIO
  8. import random
  9. import os
  10.  
  11. BIG = 100000
  12.  
  13. def fail():
  14.     raise SyntaxError
  15.     yield 1
  16.  
  17. class TestBasic(unittest.TestCase):
  18.  
  19.     def test_basics(self):
  20.         d = deque(xrange(100))
  21.         d.__init__(xrange(100, 200))
  22.         for i in xrange(200, 400):
  23.             d.append(i)
  24.         for i in reversed(xrange(-200, 0)):
  25.             d.appendleft(i)
  26.         self.assertEqual(list(d), range(-200, 400))
  27.         self.assertEqual(len(d), 600)
  28.  
  29.         left = [d.popleft() for i in xrange(250)]
  30.         self.assertEqual(left, range(-200, 50))
  31.         self.assertEqual(list(d), range(50, 400))
  32.  
  33.         right = [d.pop() for i in xrange(250)]
  34.         right.reverse()
  35.         self.assertEqual(right, range(150, 400))
  36.         self.assertEqual(list(d), range(50, 150))
  37.  
  38.     def test_comparisons(self):
  39.         d = deque('xabc'); d.popleft()
  40.         for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
  41.             self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
  42.             self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
  43.  
  44.         args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
  45.         for x in args:
  46.             for y in args:
  47.                 self.assertEqual(x == y, list(x) == list(y), (x,y))
  48.                 self.assertEqual(x != y, list(x) != list(y), (x,y))
  49.                 self.assertEqual(x <  y, list(x) <  list(y), (x,y))
  50.                 self.assertEqual(x <= y, list(x) <= list(y), (x,y))
  51.                 self.assertEqual(x >  y, list(x) >  list(y), (x,y))
  52.                 self.assertEqual(x >= y, list(x) >= list(y), (x,y))
  53.                 self.assertEqual(cmp(x,y), cmp(list(x),list(y)), (x,y))
  54.  
  55.     def test_extend(self):
  56.         d = deque('a')
  57.         self.assertRaises(TypeError, d.extend, 1)
  58.         d.extend('bcd')
  59.         self.assertEqual(list(d), list('abcd'))
  60.  
  61.     def test_extendleft(self):
  62.         d = deque('a')
  63.         self.assertRaises(TypeError, d.extendleft, 1)
  64.         d.extendleft('bcd')
  65.         self.assertEqual(list(d), list(reversed('abcd')))
  66.         d = deque()
  67.         d.extendleft(range(1000))
  68.         self.assertEqual(list(d), list(reversed(range(1000))))
  69.         self.assertRaises(SyntaxError, d.extendleft, fail())
  70.  
  71.     def test_getitem(self):
  72.         n = 200
  73.         d = deque(xrange(n))
  74.         l = range(n)
  75.         for i in xrange(n):
  76.             d.popleft()
  77.             l.pop(0)
  78.             if random.random() < 0.5:
  79.                 d.append(i)
  80.                 l.append(i)
  81.             for j in xrange(1-len(l), len(l)):
  82.                 assert d[j] == l[j]
  83.  
  84.         d = deque('superman')
  85.         self.assertEqual(d[0], 's')
  86.         self.assertEqual(d[-1], 'n')
  87.         d = deque()
  88.         self.assertRaises(IndexError, d.__getitem__, 0)
  89.         self.assertRaises(IndexError, d.__getitem__, -1)
  90.  
  91.     def test_setitem(self):
  92.         n = 200
  93.         d = deque(xrange(n))
  94.         for i in xrange(n):
  95.             d[i] = 10 * i
  96.         self.assertEqual(list(d), [10*i for i in xrange(n)])
  97.         l = list(d)
  98.         for i in xrange(1-n, 0, -1):
  99.             d[i] = 7*i
  100.             l[i] = 7*i
  101.         self.assertEqual(list(d), l)
  102.  
  103.     def test_delitem(self):
  104.         n = 500         # O(n**2) test, don't make this too big
  105.         d = deque(xrange(n))
  106.         self.assertRaises(IndexError, d.__delitem__, -n-1)
  107.         self.assertRaises(IndexError, d.__delitem__, n)
  108.         for i in xrange(n):
  109.             self.assertEqual(len(d), n-i)
  110.             j = random.randrange(-len(d), len(d))
  111.             val = d[j]
  112.             self.assert_(val in d)
  113.             del d[j]
  114.             self.assert_(val not in d)
  115.         self.assertEqual(len(d), 0)
  116.  
  117.     def test_rotate(self):
  118.         s = tuple('abcde')
  119.         n = len(s)
  120.  
  121.         d = deque(s)
  122.         d.rotate(1)             # verify rot(1)
  123.         self.assertEqual(''.join(d), 'eabcd')
  124.  
  125.         d = deque(s)
  126.         d.rotate(-1)            # verify rot(-1)
  127.         self.assertEqual(''.join(d), 'bcdea')
  128.         d.rotate()              # check default to 1
  129.         self.assertEqual(tuple(d), s)
  130.  
  131.         for i in xrange(n*3):
  132.             d = deque(s)
  133.             e = deque(d)
  134.             d.rotate(i)         # check vs. rot(1) n times
  135.             for j in xrange(i):
  136.                 e.rotate(1)
  137.             self.assertEqual(tuple(d), tuple(e))
  138.             d.rotate(-i)        # check that it works in reverse
  139.             self.assertEqual(tuple(d), s)
  140.             e.rotate(n-i)       # check that it wraps forward
  141.             self.assertEqual(tuple(e), s)
  142.  
  143.         for i in xrange(n*3):
  144.             d = deque(s)
  145.             e = deque(d)
  146.             d.rotate(-i)
  147.             for j in xrange(i):
  148.                 e.rotate(-1)    # check vs. rot(-1) n times
  149.             self.assertEqual(tuple(d), tuple(e))
  150.             d.rotate(i)         # check that it works in reverse
  151.             self.assertEqual(tuple(d), s)
  152.             e.rotate(i-n)       # check that it wraps backaround
  153.             self.assertEqual(tuple(e), s)
  154.  
  155.         d = deque(s)
  156.         e = deque(s)
  157.         e.rotate(BIG+17)        # verify on long series of rotates
  158.         dr = d.rotate
  159.         for i in xrange(BIG+17):
  160.             dr()
  161.         self.assertEqual(tuple(d), tuple(e))
  162.  
  163.         self.assertRaises(TypeError, d.rotate, 'x')   # Wrong arg type
  164.         self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
  165.  
  166.         d = deque()
  167.         d.rotate()              # rotate an empty deque
  168.         self.assertEqual(d, deque())
  169.  
  170.     def test_len(self):
  171.         d = deque('ab')
  172.         self.assertEqual(len(d), 2)
  173.         d.popleft()
  174.         self.assertEqual(len(d), 1)
  175.         d.pop()
  176.         self.assertEqual(len(d), 0)
  177.         self.assertRaises(IndexError, d.pop)
  178.         self.assertEqual(len(d), 0)
  179.         d.append('c')
  180.         self.assertEqual(len(d), 1)
  181.         d.appendleft('d')
  182.         self.assertEqual(len(d), 2)
  183.         d.clear()
  184.         self.assertEqual(len(d), 0)
  185.  
  186.     def test_underflow(self):
  187.         d = deque()
  188.         self.assertRaises(IndexError, d.pop)
  189.         self.assertRaises(IndexError, d.popleft)
  190.  
  191.     def test_clear(self):
  192.         d = deque(xrange(100))
  193.         self.assertEqual(len(d), 100)
  194.         d.clear()
  195.         self.assertEqual(len(d), 0)
  196.         self.assertEqual(list(d), [])
  197.         d.clear()               # clear an emtpy deque
  198.         self.assertEqual(list(d), [])
  199.  
  200.     def test_repr(self):
  201.         d = deque(xrange(200))
  202.         e = eval(repr(d))
  203.         self.assertEqual(list(d), list(e))
  204.         d.append(d)
  205.         self.assert_('...' in repr(d))
  206.  
  207.     def test_print(self):
  208.         d = deque(xrange(200))
  209.         d.append(d)
  210.         try:
  211.             fo = open(test_support.TESTFN, "wb")
  212.             print >> fo, d,
  213.             fo.close()
  214.             fo = open(test_support.TESTFN, "rb")
  215.             self.assertEqual(fo.read(), repr(d))
  216.         finally:
  217.             fo.close()
  218.             os.remove(test_support.TESTFN)
  219.  
  220.     def test_init(self):
  221.         self.assertRaises(TypeError, deque, 'abc', 2);
  222.         self.assertRaises(TypeError, deque, 1);
  223.  
  224.     def test_hash(self):
  225.         self.assertRaises(TypeError, hash, deque('abc'))
  226.  
  227.     def test_long_steadystate_queue_popleft(self):
  228.         for size in (0, 1, 2, 100, 1000):
  229.             d = deque(xrange(size))
  230.             append, pop = d.append, d.popleft
  231.             for i in xrange(size, BIG):
  232.                 append(i)
  233.                 x = pop()
  234.                 if x != i - size:
  235.                     self.assertEqual(x, i-size)
  236.             self.assertEqual(list(d), range(BIG-size, BIG))
  237.  
  238.     def test_long_steadystate_queue_popright(self):
  239.         for size in (0, 1, 2, 100, 1000):
  240.             d = deque(reversed(xrange(size)))
  241.             append, pop = d.appendleft, d.pop
  242.             for i in xrange(size, BIG):
  243.                 append(i)
  244.                 x = pop()
  245.                 if x != i - size:
  246.                     self.assertEqual(x, i-size)
  247.             self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG))
  248.  
  249.     def test_big_queue_popleft(self):
  250.         pass
  251.         d = deque()
  252.         append, pop = d.append, d.popleft
  253.         for i in xrange(BIG):
  254.             append(i)
  255.         for i in xrange(BIG):
  256.             x = pop()
  257.             if x != i:
  258.                 self.assertEqual(x, i)
  259.  
  260.     def test_big_queue_popright(self):
  261.         d = deque()
  262.         append, pop = d.appendleft, d.pop
  263.         for i in xrange(BIG):
  264.             append(i)
  265.         for i in xrange(BIG):
  266.             x = pop()
  267.             if x != i:
  268.                 self.assertEqual(x, i)
  269.  
  270.     def test_big_stack_right(self):
  271.         d = deque()
  272.         append, pop = d.append, d.pop
  273.         for i in xrange(BIG):
  274.             append(i)
  275.         for i in reversed(xrange(BIG)):
  276.             x = pop()
  277.             if x != i:
  278.                 self.assertEqual(x, i)
  279.         self.assertEqual(len(d), 0)
  280.  
  281.     def test_big_stack_left(self):
  282.         d = deque()
  283.         append, pop = d.appendleft, d.popleft
  284.         for i in xrange(BIG):
  285.             append(i)
  286.         for i in reversed(xrange(BIG)):
  287.             x = pop()
  288.             if x != i:
  289.                 self.assertEqual(x, i)
  290.         self.assertEqual(len(d), 0)
  291.  
  292.     def test_roundtrip_iter_init(self):
  293.         d = deque(xrange(200))
  294.         e = deque(d)
  295.         self.assertNotEqual(id(d), id(e))
  296.         self.assertEqual(list(d), list(e))
  297.  
  298.     def test_pickle(self):
  299.         d = deque(xrange(200))
  300.         for i in (0, 1, 2):
  301.             s = pickle.dumps(d, i)
  302.             e = pickle.loads(s)
  303.             self.assertNotEqual(id(d), id(e))
  304.             self.assertEqual(list(d), list(e))
  305.  
  306.     def test_pickle_recursive(self):
  307.         d = deque('abc')
  308.         d.append(d)
  309.         for i in (0, 1, 2):
  310.             e = pickle.loads(pickle.dumps(d, i))
  311.             self.assertNotEqual(id(d), id(e))
  312.             self.assertEqual(id(e), id(e[-1]))
  313.  
  314.     def test_deepcopy(self):
  315.         mut = [10]
  316.         d = deque([mut])
  317.         e = copy.deepcopy(d)
  318.         self.assertEqual(list(d), list(e))
  319.         mut[0] = 11
  320.         self.assertNotEqual(id(d), id(e))
  321.         self.assertNotEqual(list(d), list(e))
  322.  
  323.     def test_copy(self):
  324.         mut = [10]
  325.         d = deque([mut])
  326.         e = copy.copy(d)
  327.         self.assertEqual(list(d), list(e))
  328.         mut[0] = 11
  329.         self.assertNotEqual(id(d), id(e))
  330.         self.assertEqual(list(d), list(e))
  331.  
  332.     def test_reversed(self):
  333.         for s in ('abcd', xrange(2000)):
  334.             self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
  335.  
  336.     def test_gc_doesnt_blowup(self):
  337.         import gc
  338.         # This used to assert-fail in deque_traverse() under a debug
  339.         # build, or run wild with a NULL pointer in a release build.
  340.         d = deque()
  341.         for i in xrange(100):
  342.             d.append(1)
  343.             gc.collect()
  344.  
  345. def R(seqn):
  346.     'Regular generator'
  347.     for i in seqn:
  348.         yield i
  349.  
  350. class G:
  351.     'Sequence using __getitem__'
  352.     def __init__(self, seqn):
  353.         self.seqn = seqn
  354.     def __getitem__(self, i):
  355.         return self.seqn[i]
  356.  
  357. class I:
  358.     'Sequence using iterator protocol'
  359.     def __init__(self, seqn):
  360.         self.seqn = seqn
  361.         self.i = 0
  362.     def __iter__(self):
  363.         return self
  364.     def next(self):
  365.         if self.i >= len(self.seqn): raise StopIteration
  366.         v = self.seqn[self.i]
  367.         self.i += 1
  368.         return v
  369.  
  370. class Ig:
  371.     'Sequence using iterator protocol defined with a generator'
  372.     def __init__(self, seqn):
  373.         self.seqn = seqn
  374.         self.i = 0
  375.     def __iter__(self):
  376.         for val in self.seqn:
  377.             yield val
  378.  
  379. class X:
  380.     'Missing __getitem__ and __iter__'
  381.     def __init__(self, seqn):
  382.         self.seqn = seqn
  383.         self.i = 0
  384.     def next(self):
  385.         if self.i >= len(self.seqn): raise StopIteration
  386.         v = self.seqn[self.i]
  387.         self.i += 1
  388.         return v
  389.  
  390. class N:
  391.     'Iterator missing next()'
  392.     def __init__(self, seqn):
  393.         self.seqn = seqn
  394.         self.i = 0
  395.     def __iter__(self):
  396.         return self
  397.  
  398. class E:
  399.     'Test propagation of exceptions'
  400.     def __init__(self, seqn):
  401.         self.seqn = seqn
  402.         self.i = 0
  403.     def __iter__(self):
  404.         return self
  405.     def next(self):
  406.         3 // 0
  407.  
  408. class S:
  409.     'Test immediate stop'
  410.     def __init__(self, seqn):
  411.         pass
  412.     def __iter__(self):
  413.         return self
  414.     def next(self):
  415.         raise StopIteration
  416.  
  417. from itertools import chain, imap
  418. def L(seqn):
  419.     'Test multiple tiers of iterators'
  420.     return chain(imap(lambda x:x, R(Ig(G(seqn)))))
  421.  
  422.  
  423. class TestVariousIteratorArgs(unittest.TestCase):
  424.  
  425.     def test_constructor(self):
  426.         for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
  427.             for g in (G, I, Ig, S, L, R):
  428.                 self.assertEqual(list(deque(g(s))), list(g(s)))
  429.             self.assertRaises(TypeError, deque, X(s))
  430.             self.assertRaises(TypeError, deque, N(s))
  431.             self.assertRaises(ZeroDivisionError, deque, E(s))
  432.  
  433.     def test_iter_with_altered_data(self):
  434.         d = deque('abcdefg')
  435.         it = iter(d)
  436.         d.pop()
  437.         self.assertRaises(RuntimeError, it.next)
  438.  
  439. class Deque(deque):
  440.     pass
  441.  
  442. class DequeWithBadIter(deque):
  443.     def __iter__(self):
  444.         raise TypeError
  445.  
  446. class TestSubclass(unittest.TestCase):
  447.  
  448.     def test_basics(self):
  449.         d = Deque(xrange(100))
  450.         d.__init__(xrange(100, 200))
  451.         for i in xrange(200, 400):
  452.             d.append(i)
  453.         for i in reversed(xrange(-200, 0)):
  454.             d.appendleft(i)
  455.         self.assertEqual(list(d), range(-200, 400))
  456.         self.assertEqual(len(d), 600)
  457.  
  458.         left = [d.popleft() for i in xrange(250)]
  459.         self.assertEqual(left, range(-200, 50))
  460.         self.assertEqual(list(d), range(50, 400))
  461.  
  462.         right = [d.pop() for i in xrange(250)]
  463.         right.reverse()
  464.         self.assertEqual(right, range(150, 400))
  465.         self.assertEqual(list(d), range(50, 150))
  466.  
  467.         d.clear()
  468.         self.assertEqual(len(d), 0)
  469.  
  470.     def test_copy_pickle(self):
  471.  
  472.         d = Deque('abc')
  473.  
  474.         e = d.__copy__()
  475.         self.assertEqual(type(d), type(e))
  476.         self.assertEqual(list(d), list(e))
  477.  
  478.         e = Deque(d)
  479.         self.assertEqual(type(d), type(e))
  480.         self.assertEqual(list(d), list(e))
  481.  
  482.         s = pickle.dumps(d)
  483.         e = pickle.loads(s)
  484.         self.assertNotEqual(id(d), id(e))
  485.         self.assertEqual(type(d), type(e))
  486.         self.assertEqual(list(d), list(e))
  487.  
  488.     def test_pickle(self):
  489.         d = Deque('abc')
  490.         d.append(d)
  491.  
  492.         e = pickle.loads(pickle.dumps(d))
  493.         self.assertNotEqual(id(d), id(e))
  494.         self.assertEqual(type(d), type(e))
  495.         dd = d.pop()
  496.         ee = e.pop()
  497.         self.assertEqual(id(e), id(ee))
  498.         self.assertEqual(d, e)
  499.  
  500.         d.x = d
  501.         e = pickle.loads(pickle.dumps(d))
  502.         self.assertEqual(id(e), id(e.x))
  503.  
  504.         d = DequeWithBadIter('abc')
  505.         self.assertRaises(TypeError, pickle.dumps, d)
  506.  
  507.     def test_weakref(self):
  508.         d = deque('gallahad')
  509.         p = proxy(d)
  510.         self.assertEqual(str(p), str(d))
  511.         d = None
  512.         self.assertRaises(ReferenceError, str, p)
  513.  
  514.     def test_strange_subclass(self):
  515.         class X(deque):
  516.             def __iter__(self):
  517.                 return iter([])
  518.         d1 = X([1,2,3])
  519.         d2 = X([4,5,6])
  520.         d1 == d2   # not clear if this is supposed to be True or False,
  521.                    # but it used to give a SystemError
  522.  
  523. #==============================================================================
  524.  
  525. libreftest = """
  526. Example from the Library Reference:  Doc/lib/libcollections.tex
  527.  
  528. >>> from collections import deque
  529. >>> d = deque('ghi')                 # make a new deque with three items
  530. >>> for elem in d:                   # iterate over the deque's elements
  531. ...     print elem.upper()
  532. G
  533. H
  534. I
  535. >>> d.append('j')                    # add a new entry to the right side
  536. >>> d.appendleft('f')                # add a new entry to the left side
  537. >>> d                                # show the representation of the deque
  538. deque(['f', 'g', 'h', 'i', 'j'])
  539. >>> d.pop()                          # return and remove the rightmost item
  540. 'j'
  541. >>> d.popleft()                      # return and remove the leftmost item
  542. 'f'
  543. >>> list(d)                          # list the contents of the deque
  544. ['g', 'h', 'i']
  545. >>> d[0]                             # peek at leftmost item
  546. 'g'
  547. >>> d[-1]                            # peek at rightmost item
  548. 'i'
  549. >>> list(reversed(d))                # list the contents of a deque in reverse
  550. ['i', 'h', 'g']
  551. >>> 'h' in d                         # search the deque
  552. True
  553. >>> d.extend('jkl')                  # add multiple elements at once
  554. >>> d
  555. deque(['g', 'h', 'i', 'j', 'k', 'l'])
  556. >>> d.rotate(1)                      # right rotation
  557. >>> d
  558. deque(['l', 'g', 'h', 'i', 'j', 'k'])
  559. >>> d.rotate(-1)                     # left rotation
  560. >>> d
  561. deque(['g', 'h', 'i', 'j', 'k', 'l'])
  562. >>> deque(reversed(d))               # make a new deque in reverse order
  563. deque(['l', 'k', 'j', 'i', 'h', 'g'])
  564. >>> d.clear()                        # empty the deque
  565. >>> d.pop()                          # cannot pop from an empty deque
  566. Traceback (most recent call last):
  567.   File "<pyshell#6>", line 1, in -toplevel-
  568.     d.pop()
  569. IndexError: pop from an empty deque
  570.  
  571. >>> d.extendleft('abc')              # extendleft() reverses the input order
  572. >>> d
  573. deque(['c', 'b', 'a'])
  574.  
  575.  
  576.  
  577. >>> def delete_nth(d, n):
  578. ...     d.rotate(-n)
  579. ...     d.popleft()
  580. ...     d.rotate(n)
  581. ...
  582. >>> d = deque('abcdef')
  583. >>> delete_nth(d, 2)   # remove the entry at d[2]
  584. >>> d
  585. deque(['a', 'b', 'd', 'e', 'f'])
  586.  
  587.  
  588.  
  589. >>> def roundrobin(*iterables):
  590. ...     pending = deque(iter(i) for i in iterables)
  591. ...     while pending:
  592. ...         task = pending.popleft()
  593. ...         try:
  594. ...             yield task.next()
  595. ...         except StopIteration:
  596. ...             continue
  597. ...         pending.append(task)
  598. ...
  599.  
  600. >>> for value in roundrobin('abc', 'd', 'efgh'):
  601. ...     print value
  602. ...
  603. a
  604. d
  605. e
  606. b
  607. f
  608. c
  609. g
  610. h
  611.  
  612.  
  613. >>> def maketree(iterable):
  614. ...     d = deque(iterable)
  615. ...     while len(d) > 1:
  616. ...         pair = [d.popleft(), d.popleft()]
  617. ...         d.append(pair)
  618. ...     return list(d)
  619. ...
  620. >>> print maketree('abcdefgh')
  621. [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
  622.  
  623. """
  624.  
  625.  
  626. #==============================================================================
  627.  
  628. __test__ = {'libreftest' : libreftest}
  629.  
  630. def test_main(verbose=None):
  631.     import sys
  632.     test_classes = (
  633.         TestBasic,
  634.         TestVariousIteratorArgs,
  635.         TestSubclass,
  636.     )
  637.  
  638.     test_support.run_unittest(*test_classes)
  639.  
  640.     # verify reference counting
  641.     if verbose and hasattr(sys, "gettotalrefcount"):
  642.         import gc
  643.         counts = [None] * 5
  644.         for i in xrange(len(counts)):
  645.             test_support.run_unittest(*test_classes)
  646.             gc.collect()
  647.             counts[i] = sys.gettotalrefcount()
  648.         print counts
  649.  
  650.     # doctests
  651.     from test import test_deque
  652.     test_support.run_doctest(test_deque, verbose)
  653.  
  654. if __name__ == "__main__":
  655.     test_main(verbose=True)
  656.